package P2分治回溯;

import P1线性结构.LinkedList;

//迷宫
public class Maze {
    //迷宫的数组 1 表示墙；0 表示路
    private static int[][] maze = {
            {1, 1, 1, 1, 1, 1, 1, 1, 1},
            {0, 0, 1, 0, 0, 0, 1, 1, 1},
            {1, 0, 1, 1, 1, 0, 1, 1, 1},
            {1, 0, 0, 1, 0, 0, 1, 1, 1},
            {1, 1, 0, 1, 1, 0, 0, 0, 1},
            {1, 0, 0, 1, 0, 0, 1, 0, 1},
            {1, 0, 1, 0, 1, 0, 0, 0, 1},
            {1, 1, 0, 0, 0, 0, 1, 0, 0},
            {1, 1, 1, 1, 1, 1, 1, 1, 1}
    };
    //入口和出口的坐标
    private static int enterX = 1;
    private static int enterY = 0;
    private static int exitX = 7;
    private static int exitY = 8;
    //栈存储路径
    private static LinkedList<String> stack = new LinkedList();
    //道路的访问状态 false表示没走过； true表示走过了  默认全是false
    private static boolean[][] visited = new boolean[9][9];
    //方向变化量数组
    private static int direction[][] = {
            {-1, 0},
            {0, 1},
            {1, 0},
            {0, -1}
    };

    /*
    direction[0]  {-1, 0}   上
    direction[1]  {0, 1}    右
    direction[2]  {1, 0}    下
    direction[3]  {0, -1}   左
        for i 0~3
            x + direction[i][0]
            y + direction[i][1]
    */
    public static void main(String[] args) {
        if (go(enterX, enterY)) {
            System.out.println(stack);
        } else {
            System.out.println("迷宫无解");
        }
    }

    private static boolean go(int x, int y) {
        stack.push("(" + x + "," + y + ")");
        visited[x][y] = true;
        if (x == exitX && y == exitY) {
            return true;
        }
        //不是出口 遍历四个方向
        for (int i = 0; i < direction.length; i++) {
            //nx ny 是第i个方向格子的坐标
            int nx = x + direction[i][0];
            int ny = y + direction[i][1];
            if (isInArea(nx, ny) && maze[nx][ny] == 0 && !visited[nx][ny]) {
                if (go(nx, ny)) {
                    return true;
                }
            }
        }
        //for循环正常执行结束 且没有任何return true 那就表示当前x-y不通
        stack.pop();
        //因为当前x-y的四个方向都不通 那么x-y本身也不通 需要向上返回false
        return false;
    }

    private static boolean isInArea(int x, int y) {
        return x >= 0 && x < 9 && y >= 0 && y < 9;
    }
}
